//
//  SortExt.m
//  Study
//
//  Created by 振兴 刘 on 2017/9/25.
//  Copyright © 2017年 振兴 刘. All rights reserved.
//

#import "SortExt.h"

@implementation SortExt

+ (void)swap:(NSMutableArray*)array first:(NSInteger)first second:(NSInteger)second {
    
    if (first == second)
        return;
    
    if (first < 0 || second < 0)
        return;
    
    NSInteger max = array.count;
    if (first >= max || second >= max)
        return;
    
    id temp;
    temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

+ (void)heapify:(NSMutableArray*)array size:(NSInteger)size index:(NSInteger)index {
    
    NSInteger max = index;
    NSInteger left = 2*index +1;
    NSInteger right = 2*index +2;
    
    if (left < size && array[left] > array[max])
        max = left;
    
    if (right < size && array[right] > array[max])
        max = right;
    
    if (max != index) {
        [self swap:array first:index second:max];
        [self heapify:array size:size index:max];
    }
}

+ (void)buildHeap:(NSMutableArray*)array size:(NSInteger)size {
    
    for (NSInteger i = (size-1)/2 ; i >= 0; i--) {
        
        [self heapify:array size:array.count index:i];
    }
}

+ (void)heapSort:(NSMutableArray*)array {
    
    for (NSInteger i = array.count -1; i >= 0; i--) {
        
        [self buildHeap:array size:i+1];
        [self swap:array first:0 second:i];
    }
}

+ (void)quilkSort:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right {
    
    NSInteger i = left;
    NSInteger j = right;
    NSInteger pivot = (i+j)/2;
    
    while (i <= j) {
        
        while ([array[i] intValue] < [array[pivot] intValue]) {
            i++;
        }
        
        while ([array[j] intValue] > [array[pivot] intValue]) {
            j--;
        }
        
        if (i <= j) {
            [self swap:array first:i second:j];
            i++;
            j--;
        }
        
        
        if (left < j)
            [self quilkSort:array left:left right:j];
        
        if (right > i)
            [self quilkSort:array left:i right:right];
    }
}

@end
